<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>CS 5431 Spring 2011: Practicum in System Security</title>
<meta name="keywords" content="security,practical,practicum,5431,cornell,clarkson" />
<meta name="description" content="Course website at Cornell University for CS 5431" />
<meta name="author" content="Michael Clarkson" />
<link rel="stylesheet" href="http://www.cs.cornell.edu/courses/cs5431/2011sp/style.css" />
<link rel="shortcut icon" href="http://www.cornell.edu/favicon.ico" />
</head>

<body>
<div id="canvas">

<div id="header">
<div id="info">
<a href="http://www.cs.cornell.edu/courses/cs5431/2011sp">
<span class="title">CS 5431</span><br />
<span class="subtitle">Practicum in System Security</span>
</a>
</div>

<div id="logo"> 
<a href="http://www.cs.cornell.edu">
<img src="http://www.cs.cornell.edu/courses/cs5431/2011sp/images/cslogo.png" alt="Cornell Computer Science" />
</a>
</div>
</div><!--end header-->

<div style="clear:both;"></div>

<div id="menu"> 
  <ul>
    <li><a href="index.php">Home</a></li>
    <li><a href="readings.php">Readings</a></li>
    <li><a href="syllabus.php">Syllabus</a></li>
  </ul>
</div>

<div class="content">


<h1>Homework 2:  Part II</h1>

<p>Due: <span class="duedate">Thursday, March 31, 10:00 pm</span>
through <a href="http://cms.csuglab.cornell.edu">CMS</a>.</p>

<blockquote>
<p><i>Few false ideas have more firmly gripped the minds of so many 
intelligent men than the one that, if they just tried, they could 
invent a cipher that no one could break.</i> 
&mdash;David Kahn</p>
<p><i>In the past decade, cryptography has done more to damage the
security of digital systems than it has to enhance it.</i>
&mdash;Ferguson &amp; Schneier, 2003</p>
</blockquote>

<h3>0. Hybrid Decryption</h3>

<p>If you're reading this plaintext, 
you've already solved Part I of this homework.</p>

<p><span class="phead">What to submit:</span> a directory 
named <tt>hybrid</tt> containing your implementation that
decrypted Part II.
That directory should contain a text file named <tt>README</tt> with very
clear documentation on how to run your program(s).</p>

<h3>1. DES Cracker</h3>

<p>The following file was encrypted with DES in ECB mode (oh no!) with
PKCS5 padding:  <a href="http://www.cs.cornell.edu/courses/cs5431/2011sp/hw2/hw2des.bin"><tt>hw2des.bin</tt></a>.
The file contains the raw bytes output from the DES encryption.
All the bits of the encryption key were set to 0, except for the first
two bytes of the key.  Those two bytes could be anything.</p>

<p>Write a program (or set of programs) that cracks the DES encryption by recovering
the plaintext and encryption key.  You may use
a mixture of Java programs, scripts, etc., if you like,
or you may keep your implementation entirely in Java.  It's okay for
your program to output a <b>small</b> handful of possible decryptions and have a human
manually inspect them as the final step of the crack.
Hint:  the plaintext contains English words.</p>

<p><span class="phead">What to submit:</span> a directory 
named <tt>crack</tt> containing your implementation.
That directory should contain a text file named <tt>README</tt> with very
clear documentation on how to run your program(s).  
Your directory should also include a file named <tt>answer.txt</tt>
containing the plaintext and the key, formatted in ASCII.</p>

<h3>2. Membership Directory</h3>

<p>You are the secretary of a secret society named Kappa Rho Upsilon (aka κρυπτός),
and you are preparing to publish the membership directory of the society.
That directory contains each member's last name and email address.
However, the members of Kappa Rho Upsilon are very concerned about their 
privacy.  They don't want you to publish the directory in plaintext.</p>

<p>You propose to publish the directory encrypted with a symmetric cipher,
and to distribute the shared key to everyone at your next meeting.
Although they agree to the notion of sharing a key, the members 
don't trust one another.  What if a lazy, untrustworthy member 
decrypts the whole directory and leaves it sitting on their hard drive?
A Trojan Horse might steal the entire plaintext directory.  So the members 
reject your proposal.</p>

<p>They challenge you to invent a scheme in which
it is easy&mdash;meaning O(1) decryptions&mdash;to extract the email 
address of a single member if you know their last name, but
hard&mdash;meaning O(<i>n</i>) decryptions, where <i>n</i> is the number of members&mdash;to 
extract the email addresses of all members.  No names should appear in plaintext
in the directory.</p>

<p>Implement your scheme in Java.  Write a program with which a user can query
the directory for a given last name and retrieve the associated email
address (if any).</p>

<p><span class="phead">What to submit:</span> a directory 
named <tt>kru</tt> containing your Java implementation.
That directory should contain a text file named <tt>README</tt> with very
clear documentation on how to run your program(s).  It should take 
a TA no more than one minute to successfully follow your documentation.
Include a sample membership directory with which a TA can test your implementation.
You should also provide a text or PDF file named <tt>DESIGN.txt</tt>
or <tt>DESIGN.pdf</tt>.  This file should clearly describe the security 
aspects of your design, including how you employed cryptography.  Justify
your choices of algorithms, key lengths, nonce lengths, etc.</p>

<h3>3. Needham-Schroeder-Lowe</h3>

<p>Implement the following version of the Needham-Schroeder-Lowe (NSL) public-key 
protocol for authentication:</p>

<pre>
1. A->B: Enc(A, N_A; K_B)
2. B->A: Enc(B, N_A, N_B; K_A)
3. A->B: Enc(N_B; K_B)
</pre>

<p>(This protocol, or a version of it, will be discussed in CS 5430.)
Here, key <tt>K_X</tt> is the public key of principal <tt>X</tt>, and
nonce <tt>N_X</tt> is invented as a challenge by principal <tt>X</tt>.
</p>

<p><b>To get a maximum grade of B+ on the entire homework:</b>
Your implementation should involve two programs,  Alice and Bob.  
Each program should display the messages it sends and should 
indicate whether the other principal was successfully authenticated.
It should be possible to inject errors that cause authentication to fail.</p>

<p><b>To get a maximum grade of A+ on the entire homework:</b>
Your implementation should involve three programs:  Alice, Bob, and Mallory.
Alice and Bob are the programs trying to authenticate one another.  Mallory
is a Dolev&ndash;Yao attacker who can read, modify, and delete messages from the network.
Arrange the TCP communication of your programs such that Alice and Bob both 
send their messages to, and receive them from, Mallory.
Your programs should make it easy to demonstrate how NSL works to someone
who hasn't seen it before.  For example:</p>
<ul>
<li>You could require the user to click or press something to send each message.</li>
<li>You could make it possible to operate the programs with and without encryption,
so that the plaintext messages can be seen.</li>
<li>You could enable Mallory to change messages.</li>
</ul>

<p><span class="phead">What to submit:</span> a directory 
named <tt>nsl</tt> containing your Java implementation.
That directory should contain a text file named <tt>README</tt> with very
clear documentation on how to run your program(s).  It should take 
a TA no more than a couple minutes to successfully follow your documentation.
Your directory should also contain a text or PDF file named <tt>DESIGN.txt</tt>
or <tt>DESIGN.pdf</tt>.  This file should clearly describe the security 
aspects of your design, including how you employed cryptography.  Justify
your choices of algorithms, key lengths, nonce lengths, etc.</p>

<h3>4. Digital Signature</h3>

<p>Generate an RSA key pair.  Name the public key file
<tt>rsa_ver.bin</tt> and the private key file <tt>rsa_sign.bin</tt>.
Build a program that signs and verifies signatures.
Sign your submission file <tt>hw2.zip</tt>
with the signing key.</p>

<p><span class="phead">What to submit:</span> a directory 
named <tt>sign</tt> containing your Java implementation.
That directory should contain a text file named <tt>README</tt> with very
clear documentation on how to run your program(s).  It should take 
a TA no more than a minute to successfully follow your documentation,
including verifiying your signature on your submission.
Your directory should also contain a text or PDF file named <tt>DESIGN.txt</tt>
or <tt>DESIGN.pdf</tt>.  This file should clearly describe the security 
aspects of your design, including how you employed cryptography.  Justify
your choices of algorithms, key lengths, nonce lengths, etc.</p>

<h3>5. [Karma] RSA Timing Attack</h3>

<p><span class="duedate">This is a karma problem.  You do not have to solve it.</span></p>

<p>Study these papers:</p>
<ul>
<li><a href="http://www.cs.cornell.edu/courses/cs5431/2011sp/hw2/TimingKocher.pdf">Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems</a>. 
Paul C. Kocher.  In Proc. CRYPTO, p. 104&ndash;113, 1996. </li>
<li><a href="http://www.cs.cornell.edu/courses/cs5431/2011sp/hw2/TimingDhem.pdf">A Practical Implementation of the Timing Attack</a>.
J.-F. Dhem et al.  Universit&eacute; Catholique de Louvain Technical Report CG-1998/1, June 1998.</li>
<li><a href="http://www.cs.cornell.edu/courses/cs5431/2011sp/hw2/TimingBrumley.pdf">Remote Timing Attacks are Practical</a>.  David Brumley
and Dan Boneh.  In Proc. USENIX Security, 2003.</li>
</ul>

<p>Implement a timing attack on RSA in Java.  You won't be able to mount
a successful attack on the Sun (now Oracle) implementation of the JCA, because that implementation
uses blinding to defeat timing attacks.  However, you could install the <a href="http://www.bouncycastle.org">
bouncycastle.org</a> JCA provider, which has both blinded and non-blinded versions of RSA available.
You <b>should</b> be able to successfully attack the non-blinded version.</p>

<p>The simplest approach would be to mount a local attack, in which you time RSA operations
running on your local machine.  After that, you could try a remote attack, in which
you time RSA operations running on a remote machine.</p>

<p>The ultimate solution to this problem would be a successful attack on the Android platform,
which uses the bouncycastle.org provider.  If you succeed in this, you have an MEng project,
and I'd be happy to advise you in finishing it.</p>

<p><span class="phead">What to submit:</span> a directory 
named <tt>timing</tt> containing your implementation.
That directory should contain a text file named <tt>README</tt> with very
clear documentation of your attacks.  You may be asked to meet
with the instructor to demonstrate your attacks.</p>

<h3>Submission</h3>

<p>Submit a file named <tt>hw2.zip</tt> containing all the folders
described above, a file named <tt>hw2zip.sig</tt> containing the raw bytes
of your signature on <tt>hw2.zip</tt>, and a file named <tt>rsa_ver.bin</tt>
containing the raw bytes of an X509 encoding of your signature 
verification key.</p>

</div><!--end content-->
</div><!--end canvas-->

</body>
</html>
